The present invention relates to a system of flushing conflicted write transactions from a memory controller.
Modern computer systems are multi-agent systems. A typical application is shown in FIG. 1. An "agent" may be a processor, a memory controller or an input/output device. Some agents, such as processors, manipulate data while others, such as memory controllers, may merely store and retrieve data. However, the agents must coordinate with each other to maintain data coherency. Thus, the agents 10-50 communicate with each other over a common bus 60 using a predetermined signaling protocol.
A memory controller system 50 is a common type of agent. The memory controller system is a common agent that controls reading and writing of data to and from a memory. Thus, when an agent (such as agent 10) requires data held in memory, it begins a bus transaction to request the data. All other agents observe the transaction and determine whether they possess the requested data. If the memory controller system 50 possesses the data, it provides the requested data on the bus 60. The first agent 10 then retrieves the requested data from the bus 60 and uses it as necessary.
The memory controller system 50 also writes data to memory. When an agent issues a bus transaction to write data to memory, the memory controller system retrieves data from the external bus.
The memory controller system generally includes a memory controller 51, a data controller 52 and the memory 53 itself. The memory controller 51 processes administrative information related to a bus transaction. For example, transactions include request identifiers that indicate the type of request being made (for example, read or write). They also include address information identifying a memory address where the transaction is directed. This administrative information is processed by the memory controller 51.
For write transactions, data to be written to memory is stored temporarily in a data controller 52, an intermediate buffer memory. Data is transferred from the data controller to memory sometime after the conclusion of the bus transaction. It is common for memory controller systems to process administrative information and data in separate paths, such as in the memory controller 51 and the data controller 52.
As is known, memories are traditionally slow devices in a computer system. Transactions may be posted on the bus faster than a memory controller may serve them. Accordingly, it is known for memory controllers to prioritize processing of requests to improve transaction throughput. Read around write ("RAW") techniques are one such priority scheme.
RAW techniques recognize that read requests have a higher priority than write requests. When another agent issues a read request, the agent typically requires the requested data to perform some operation. The agent must wait for the data to complete the operation. Any increase in the latency of the read request, the time that it takes a transaction to be completed, may impair the agent's processing performance. Write transactions, however, often are not critical. When an agent issues a write transaction, the data typically has no implication on any agent's performance. Accordingly, write transactions need not be implemented with the same priority that read transactions are implemented.
Memory controllers may include a write queue that stores write transactions to implement RAW. The write queue may be a first in, first out ("FIFO") queue. The write transactions are stored temporarily in anticipation of idle time in which the stored transactions may be performed. Read requests issued on the bus are not queued; they are processed immediately upon receipt. Thus, although a write transaction may precede a read request when observed on the bus, the memory controller may complete the read request before it completes the write request. In this case, the memory controller performs the read request around the write request.
Memory controllers monitor the bus to recognize "implicit write backs." Implicit write backs occur when a first agent 10 issues a read request directed to a particular address and a second agent 20 possesses a modified copy of data from that address. The second agent 20 may have read it from memory 52 at some point earlier and performed an operation that modified the data. There is no requirement in many multi-agent systems that an agent 20 that modifies data must also write the modified data back to memory; it may store the data in an internal cache. Typically, when a second agent 20 possesses a modified copy of data requested by a first agent 10, the second agent 20 rather than the memory controller 50 will transfer data to the first. As part of the bus protocol, the agents must engage in a cache coherency signaling protocol to identify where the most current copy of requested data is located. In the Pentium Pro.RTM. processor, "snoop signaling" is exchanged to perform this cache coherency function.
To transfer data in the implicit write back case, the second agent 20 places the modified data on the bus. The first agent 10 reads the data from the bus and processes the data. The memory controller 50 also reads the data from the bus and causes it to be written to memory. Thus, although the data is provided to the memory controller 50 during a read request, it causes data to be written to memory. It is an "implicit write back." Implicit write back and traditional writes are both treated identically within the memory controller. Both may be considered low priority transactions for RAW processing.
RAW techniques raise an additional processing issue. Occasionally, an agent issues a read request for data at an address then a write transaction to that address is pending in the write queue. The pending write transaction is considered a "conflicted write transaction." Before the read request may be completed, the conflicted write must be performed.
In the known memory controllers, the conflicted write is flushed from the write queue along with every pending write transaction stored in queue ahead of the conflicted write transaction. Thus, the memory controller identifies the queue position of the conflicted write. Then, all write transactions from the head of the write queue to and including the conflicted write are output from the queue and performed. If the conflicted write is tenth in position in the queue, for example, then ten write transactions are performed sequentially. The read request is stalled until the conflicted write transaction is performed.
The known technique of flushing conflicted write transactions imposes unnecessary latency to a read request. If T.sub.wflush is the average time required to flush a single transaction from the write queue and k is the queue position of the conflict write transaction, the read request will be stalled according to: EQU read-stall latency=k*T.sub.wflush.
These techniques impose unnecessary latency to the stalled read request because a plurality of transactions often are flushed even when it is necessary that only one transaction be flushed.
Thus, there is a need in the art for a technique of flushing conflicted write transactions that minimizes read latency. There is a need in the art for such a transaction that flushes only a conflicted write transaction from a write queue.